package leetcode.editor.cn.q1_300.q250;
//给你一个整数 n ，请你找出并返回第 n 个 丑数 。 
//
// 丑数 就是只包含质因数 2、3 和/或 5 的正整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 10
//输出：12
//解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
//解释：1 通常被视为丑数。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 1690 
// 
//
// 👍 1079 👎 0

/**
 * 思路一：
 * 所有的丑数都是由 2 3 5 相乘得到，那么第 n 个丑数，一定是由 1~n-1 个丑数中的某个数 乘以 2/3/5 得到
 * 使用容器记录前 n-1 个丑数，只需要判断当前数除以 2/3/5 是否存在容器中，如果存在那么当前数就是第 n 个丑数
 * <p>
 * 思路二：
 * 好吧，还是看了答案
 */
public class Q264_UglyNumberIi {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n + 1];
            dp[1] = 1;

            // 没有进行乘以 2/3/5 的下标
            int p2 = 1, p3 = 1, p5 = 1;
            for (int i = 2; i <= n; i++) {
                int u2 = dp[p2] * 2;
                int u3 = dp[p3] * 3;
                int u5 = dp[p5] * 5;

                dp[i] = Math.min(u2, Math.min(u3, u5));

                if (dp[i] == u2) {
                    p2++;
                }
                if (dp[i] == u3) {
                    p3++;
                }
                if (dp[i] == u5) {
                    p5++;
                }
            }

            return dp[n];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q264_UglyNumberIi().new Solution();
        // TO TEST
        int num = 0;
        for (int i = 1; i <= 1690; i++) {
            while (true) {
                num++;
                if (new Q263_UglyNumber().new Solution().isUgly(num)) {
                    int ii = solution.nthUglyNumber(i);
                    if (num != ii) {
                        System.out.println(i + "\t" + num + "\t" + ii);
                    }
                    break;
                }
            }
        }
        System.out.println("测试完成");
    }
}